package com.freedy.dataStructure.tree;

import java.util.StringJoiner;

/**
 * 排序二叉树
 * @author Freedy
 * @date 2021/4/2 16:41
 */
public class BinarySortTree {
    private Node root;

    BinarySortTree(Integer rootVal) {
        root = new Node(rootVal);
    }

    public void changeRootVal(int val){
        root.setData(val);
    }

    public void add(Integer val) {
        if (val != null) {
            Node node = new Node(val);
            root.add(node);
        }
    }

    public void print(TreeEnum mode) {
        switch (mode) {
            case preOrder -> root.preOrder();
            case infixOrder -> root.infixOrder();
            case postOrder -> root.postOrder();
            default -> throw new RuntimeException("参数不正确");
        }
    }

    public boolean del(int val){
        Node target = root.search(val);
        if (target==null) return false;
        Node parent = root.searchParent(val);
        if (parent==null){
            //表示要删除的是根节点
            if (target.getLeftNode()==null&&target.getRightNode()==null){
                //表示该树只有一个节点且是根节点，这是不能让其删除
                throw new RuntimeException("binary sort tree can not be empty");
            }else if (target.getLeftNode()==null&&target.getRightNode()!=null){
                //要删除的节点只有右子树
                root=root.getRightNode();
                return true;
            }else if (target.getLeftNode()!=null&&target.getRightNode()==null){
                //要删除的节点只有左子树
                root=root.getLeftNode();
                return true;
            }else if (target.getLeftNode()!=null&&target.getRightNode()!=null){
                //要删除的节点是有两个子树
                int minVal = delMinVal(target.getRightNode());
                target.setData(minVal);
                return true;
            }
        }else {
            if (target.getLeftNode()==null&&target.getRightNode()==null){
                //表示要删除的节点是叶子节点
                if (parent.getLeftNode()!=null&&parent.getLeftNode().getData()==val){
                    parent.setLeftNode(null);
                    return true;
                }else if (parent.getRightNode()!=null&&parent.getRightNode().getData()==val){
                    parent.setRightNode(null);
                    return true;
                }
            }else if (target.getLeftNode()==null&&target.getRightNode()!=null){
                //要删除的节点只有右子树
                if (parent.getLeftNode()!=null&&parent.getLeftNode().getData()==val){
                    //要删的节点在parent的左子树
                    parent.setLeftNode(target.getRightNode());
                    return true;
                }else if (parent.getRightNode()!=null&&parent.getRightNode().getData()==val){
                    //要删的节点在parent的右子树
                    parent.setRightNode(target.getRightNode());
                    return true;
                }
            }else if (target.getLeftNode()!=null&&target.getRightNode()==null){
                //要删除的节点只有左子树
                if (parent.getLeftNode()!=null&&parent.getLeftNode().getData()==val){
                    //要删的节点在parent的左子树
                    parent.setLeftNode(target.getLeftNode());
                    return true;
                }else if (parent.getRightNode()!=null&&parent.getRightNode().getData()==val){
                    //要删的节点在parent的右子树
                    parent.setRightNode(target.getLeftNode());
                    return true;
                }
            }else if (target.getLeftNode()!=null&&target.getRightNode()!=null){
                //要删除的节点是有两个子树
                int minVal = delMinVal(target.getRightNode());
                target.setData(minVal);
                return true;
            }
        }
        throw new RuntimeException("删除失败");
    }

    /**
     * 找到排序二叉树中最小的值，并删除
     */
    private int delMinVal(Node node){
        Node pre = null;
        while (node.getLeftNode()!=null){
            pre=node;
            node=node.getLeftNode();
        }
        Integer val = node.getData();
        if (pre!=null){
            pre.setLeftNode(null);
        }else {
            //表示node没有子节点，直接删除自己
            Node parent = root.searchParent(val);
            if (parent.getLeftNode()!=null&& parent.getLeftNode().getData().equals(val)){
                parent.setLeftNode(node.getRightNode());
            }else if (parent.getRightNode()!=null&& parent.getRightNode().getData().equals(val)){
                parent.setRightNode(node.getRightNode());
            }
        }
        return val;
    }

    private static class Node {
        private Integer data;
        private Node leftNode;
        private Node rightNode;

        //*******************************CONSTRUCT**********************************
        public Node() {
        }

        public Node(Integer data) {
            this.data = data;
        }

        public Integer getData() {
            return data;
        }

        public void setData(Integer data) {
            this.data = data;
        }

        public Node getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(Node leftNode) {
            this.leftNode = leftNode;
        }

        public Node getRightNode() {
            return rightNode;
        }

        public void setRightNode(Node rightNode) {
            this.rightNode = rightNode;
        }

        @Override
        public String toString() {
            return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]")
                    .add("data=" + data)
                    .add("leftNode=" + (leftNode == null ? "" : leftNode.hashCode()))
                    .add("rightNode=" + (rightNode == null ? "" : rightNode.hashCode()))
                    .toString();
        }
        //***********************************END***************************************

        /**
         * 添加节点
         * 递归的形式添加节点，注意需要满足的二叉排序树的要求
         */
        public void add(Node node) {
            if (node == null) return;
            if (node.getData() < this.getData()) {
                //向左边比较
                if (this.getLeftNode() == null) {
                    //无节点 直接添加
                    this.setLeftNode(node);
                } else {
                    //有节点 递归添加
                    this.getLeftNode().add(node);
                }
            } else {
                //向右边比较
                if (this.getRightNode() == null) {
                    //无节点 直接添加
                    this.setRightNode(node);
                } else {
                    //有节点 递归添加
                    this.getRightNode().add(node);
                }
            }
        }

        /**
         * 查找结点
         * @param val 要查找节点的值
         * @return 节点
         */
        public Node search(int val) {
            if (val == this.data) {
                //找到就直接返回
                return this;
            } else if (val < this.data) {
                //若果小于就去左节点继续查找
                if (this.getLeftNode()!=null){
                    return this.getLeftNode().search(val);
                }
            } else {
                //若果大于就去右节点继续查找
                if (this.getRightNode()!=null){
                    return this.getRightNode().search(val);
                }
            }
            return null;
        }

        /**
         * 返回要查找节点的父节点
         */
        public Node searchParent(int val){
            if (this.getLeftNode()!=null&&this.getLeftNode().getData()==val ||
                this.getRightNode()!=null&&this.getRightNode().getData()==val){
                //找到其父节点
                return this;
            }else {
                if (this.getData()>val){
                    //若果小于就去左节点继续查找
                    if (this.getLeftNode()!=null){
                        return this.getLeftNode().searchParent(val);
                    }
                }else{
                    //若果大于就去右节点继续查找
                    if (this.getRightNode()!=null){
                        return this.getRightNode().searchParent(val);
                    }
                }
                return null;
            }
        }

        /**
         * 前中后序遍历
         */
        public void preOrder() {
            System.out.println(this);
            if (leftNode != null) {
                leftNode.preOrder();
            }
            if (rightNode != null) {
                rightNode.preOrder();
            }
        }

        public void infixOrder() {
            if (leftNode != null) {
                leftNode.infixOrder();
            }
            System.out.println(this);
            if (rightNode != null) {
                rightNode.infixOrder();
            }
        }

        public void postOrder() {
            if (leftNode != null) {
                leftNode.postOrder();
            }
            if (rightNode != null) {
                rightNode.postOrder();
            }
            System.out.println(this);
        }

        public Boolean deleteNode(Integer data) {
            if (leftNode != null && leftNode.getData().equals(data)) {
                leftNode = null;
                return true;
            }
            if (rightNode != null && rightNode.getData().equals(data)) {
                rightNode = null;
                return true;
            }
            if (leftNode != null) {
                boolean left = leftNode.deleteNode(data);
                if (left) return true;
            }
            if (rightNode != null) {
                return rightNode.deleteNode(data);
            }
            return false;
        }

    }
}
